#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <map>
#include <set>
#include <climits>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int M = 10010;
vector <int> gragh[M];
int lucky[M], instack[M], low[M], mark[M], dfn, top, n, m, s[M];
int dfs(int k, int p)
{
	mark[k] = low[k] = dfn++;
	if (!instack[k])
	{
		instack[k] = 1;
		s[top++] = k;
	}
	int son = 0, tag = 0;
	for(unsigned int i = 0; i < gragh[k].size(); ++i)
	{
		int j = gragh[k][i];
		if (j == p)
			continue;
		if (mark[j] == 0)
		{
			dfs(j, k);
			++son;
			low[k] = min(low[k], low[j]);
			if(low[j] >= mark[k])
				tag = 1;
		}
		else
			low[k] = min(low[k], mark[j]);
	}
	if ((p != -1 && tag) || (p == -1 && son > 1))
	{
		int j = s[--top];
		int tmp[M], tt = 0;
		while (j != k)
		{
			tmp[tt++] = j;
			j = s[--top];
		}
		tmp[tt++] = j;
		if (tt % 2)
		{
			while (tt >= 0)
			{
				j = tmp[tt--];
				lucky[j] = 1;
			}
		}
	}
	return 0;
}
int main()
{
	int cases;
	scanf("%d", &cases);
	while (cases--)
	{
		top = 0;
		dfn = 1;
		scanf("%d%d", &n, &m);
		memset(instack, 0, sizeof(instack));
		memset(mark, 0, sizeof(mark));
		memset(lucky, 0, sizeof(lucky));
		for (int i = 1; i <= n; i++)
			gragh[i].clear();
		for (int i = 0; i < m; i++)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			gragh[a].push_back(b);
			gragh[b].push_back(a);
		}
		dfs(1, -1);
		int ans = 0;
		for (int i = 1; i <= n; i++)
			if (lucky[i] == 1)
				ans++;
		printf("%d\n", ans);
	}
    return 0;
}
